package leetcode.code0187;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution1 extends Solution187 {

	@Override
	public List<String> findRepeatedDnaSequences(String s) {
		int len = s.length();
		List<String> ans = new ArrayList<>();
		if (len < 11) {
			return ans;
		}
		char[] cs = s.toCharArray();
		int cur = 0;
		Map<Integer, Boolean> table = new HashMap<>();
		for (int i = 0; i < 10; i++) {
			cur = (cur << 2) | map(cs[i]);
		}
		table.put(cur, false);
		int cut = 0b11111111111111111111;
		for (int i = 10; i < len; i++) {
			cur = ((cur << 2) | map(cs[i])) & cut;
			Boolean has = table.getOrDefault(cur, null);
			if (has == null) {
				table.put(cur, false);
			} else if (!has) {
				ans.add(new String(cs, i - 9, 10));
				table.put(cur, true);
			}
		}
		return ans;
	}

	private int map(char c) {
		if (c == 'A') {
			return 0b00;
		}
		if (c == 'C') {
			return 0b01;
		}
		if (c == 'G') {
			return 0b10;
		}
		if (c == 'T') {
			return 0b11;
		}
		return -1;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();

	}

}
